1. Field of the Invention
Embodiments of the present invention generally relate to a method for optimizing the compiling of computer programs. More particularly, embodiments of the invention relate to a head-call optimization technique used to reduce the amount of stack space consumed by a computer program.
2. Description of the Related Art
Compilers are computer programs that translate source code into object code. The source code is usually composed by developers using a high-level programming language, such as the C, C++ or Java® programming languages. The object code produced by the compiler is assembly or machine language. The object code generated by the compiler is output in the format of a binary executable file. Once compiled, the program is executable, i.e., a computer can load and execute the program.
Often, compilers use a multiple-pass process to generate an executable program from program source code. First, a lexical analysis pass is used to convert the source code into an intermediate representation, consisting of small elements referred to as tokens. Some compiler applications are configured to analyze this intermediate code, to determine how the program can be optimized. The optimized code is functionally equivalent, but may run more efficiently or consume less memory space. For example, dead code elimination is a type of optimization that reduces a program's size by removing unreachable code or unused variables. Once the intermediate language has been optimized, it is translated into executable code, i.e., a sequence of machine-level instructions executable by a particular processor architecture.
Memory consumption and stack usage is an aspect of program execution that may benefit from code optimization. When a new program is executed, a memory space is allocated for the program to use. Typically, a stack space is allocated at one end of the memory space and a heap space is allocated at the other end. During program execution, the space allocated for both the stack and the heap grow towards the center of the memory space. The stack is a reserved area that stores data using a “last in, first out” data structure. The stack stores program data related to program flow, such as the program counter and each called function's local variables. The computer uses this information to resume execution at the appropriate point of a function after program control is returned from one function to another. For example, if function A calls function B, then the computer stores (“pushes”) function B data on the stack above the data for function A. If function B calls function C, then function C's data is also pushed on the stack. At this point, the stack contains data for functions A, B and C. Because the stack is a “last in, first out” data structure, the data for function C is on the “top” of the stack. Accordingly, when function C exits, function C's data is removed (“popped”) from the top of the stack, and the program resumes executing at the point of function B where it left off when function C was called. Likewise, when function B exits, function B's data is popped from the stack, and the program resumes executing at the point of function A where it left off when function B was called.